/**
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
 */

// 深度优先
let dfs = (root, sum) => {
    if (!root) return false; // 如果没有根节点，返回false
    if (!root.left && !root.right) return sum === root.val; // 判断叶子结点：左孩子和右孩子都不存在，说明是叶子结点
    return dfs(root.left, sum - root.val) || dfs(root.right, sum - root.val);
}

// 广度优先
var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    let queue = [
        [root, root.val]
    ];
    while (queue.length > 0) {
        let [node, val] = queue.shift();
        if (!node.left && !node.right) {
            if (val === targetSum) return true;
            continue;
        }
        if (node.left) {
            queue.push([node.left, node.left.val + val]);
        }
        if (node.right) {
            queue.push([node.right, node.right.val + val]);
        }
    }
    return false;
};